{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## <Simple Algorithms about LIST\\>\n",
    "## LeetCode简单算法 之 数组."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  1.从排序数组中删除重复项\n",
    "给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。\n",
    "\n",
    "不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def removeDuplicates(nums):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    nums[:] = sorted(set(nums),key=nums.index)\n",
    "    return len(nums)\n",
    "# 发现，如果把nums[:]的[:]去掉，就无法改变nums了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 其他的做法的问题：\n",
    "def removeD(nums):\n",
    "    nums[:] = list(set(nums))\n",
    "    return len(nums)\n",
    "# 这种方式可以去重，但是没法保持原来的顺序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "[0, 3, 2, 1]\n",
      "[0, 1, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "a = [0,0,3,2,1]\n",
    "l = removeDuplicates(a)\n",
    "print(l)\n",
    "print(a)\n",
    "b = [0,0,3,2,1]\n",
    "ll = removeD(b)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.买卖股票的最佳时机 II\n",
    "给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。\n",
    "\n",
    "设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。\n",
    "\n",
    "注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        v = 0\n",
    "        for i in range(len(prices)-1):\n",
    "            if prices[i+1]>prices[i]:\n",
    "                v += prices[i+1]-prices[i]\n",
    "            else:\n",
    "                pass\n",
    "        return v   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ### 3.旋转数组(平移数组)\n",
    " 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。<br>\n",
    " 输入: [1,2,3,4,5,6,7] 和 k = 3<br>\n",
    "输出: [5,6,7,1,2,3,4]<br>\n",
    "解释:<br>\n",
    "向右旋转 1 步: [7,1,2,3,4,5,6]<br>\n",
    "向右旋转 2 步: [6,7,1,2,3,4,5]<br>\n",
    "向右旋转 3 步: [5,6,7,1,2,3,4]<br>\n",
    "说明:\n",
    "- 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。\n",
    "- 要求使用空间复杂度为 O(1) 的原地算法。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 4, 1]\n"
     ]
    }
   ],
   "source": [
    "# 笨方法，而且比较耗空间，因为新建了一个变量占用空间，不是原地算法\n",
    "def my_rotate(nums, k):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :type k: int\n",
    "    :rtype: void Do not return anything, modify nums in-place instead.\n",
    "    \"\"\"\n",
    "    l = len(nums)\n",
    "    new = [0]*l      # 这里写new[]的话，下面就没法直接赋值，只能用append方法；如果要直接赋值的话，就要这样写\n",
    "    for i in range(l):\n",
    "        if i+k<l:\n",
    "            new[i] = nums[i+k]\n",
    "        else:\n",
    "            new[i] = nums[i+k-l]\n",
    "    nums[:] = new   # 这里必须写[:]，否则没法赋值\n",
    "    \n",
    "a = [1,2,3,4]\n",
    "my_rotate(a,1)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 4, 1, 2]\n"
     ]
    }
   ],
   "source": [
    "# 正确的方法之一 是使用python数组的insert和pop函数\n",
    "def rotate(nums,k):\n",
    "    for each in range(k):\n",
    "        nums.insert(0,nums.pop())\n",
    "rotate(a,2)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5]\n",
      "[1, 2, 3, 4, 5]\n",
      "--------\n",
      "[3, 4, 5]\n",
      "[1, 2]\n",
      "--------\n",
      "[4, 5]\n",
      "[1, 2, 3]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 还有效率更高的方法，不放先看看：\n",
    "b = [1,2,3,4,5]\n",
    "print(b)\n",
    "print(b[:])\n",
    "print(\"--------\")\n",
    "print(b[2:]) # index为2的和之后的\n",
    "print(b[:2]) # 从开头到index为2的\n",
    "print(\"--------\")\n",
    "print(b[-2:]) # 从倒数第二个到最后\n",
    "print(b[:-2]) # 从开头到倒数第二个\n",
    "\n",
    "b[:-2]+b[-2:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 4, 1, 2]\n"
     ]
    }
   ],
   "source": [
    "def best_rotate(nums,k):\n",
    "    i = k%len(nums)  # 这里要留意一下，为什么这么写\n",
    "    nums[:] = nums[-i:]+nums[:-i]\n",
    "a = [1,2,3,4]\n",
    "best_rotate(a,2)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 4.只出现一次的数字\n",
    "给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。<br>\n",
    "说明：<br>\n",
    "你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？\n",
    "输入: [4,1,2,1,2]<br>\n",
    "输出: 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 我的初试方法：（好像被反映效率太低）\n",
    "def singleNumber1(nums):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    for i in range(len(nums)): # 检查每一个元素\n",
    "        for j in range(len(nums)): # 和每一个其他元素进行对比\n",
    "            if i == j: # 如果是同一个元素就跳过\n",
    "                pass\n",
    "            else:      # 如果不是同一个元素：\n",
    "                if nums[i] == nums[j]: # 只要相等，就直接跳出循环,结束对num[i]的考察\n",
    "                    break\n",
    "            if j == len(nums)-1: # 已经用所有的元素检查了一遍，都没有break，才有机会进行这一步，说明已经找到了那个nums[i]\n",
    "                return nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "a = [11,11,23,23,37,37,43,43,54,54,62,62,99,99,56,56,999,999,9876,9876,5059,5059,7761,7761]*2000+[111]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "111\n",
      "Running time: 0.30854010581970215 s\n"
     ]
    }
   ],
   "source": [
    "t1 = time.time()\n",
    "print(singleNumber1(a))\n",
    "t2 = time.time()\n",
    "print(\"Running time:\",str((t2-t1)),'s')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 我的方法二：（这个方法居然出奇的慢！虽然代码量很少。看来原生的方法有着极大的优势啊！）\n",
    "def singleNumber2(nums):\n",
    "    for each in nums:\n",
    "        if nums.count(each) == 1:\n",
    "            return each"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "111\n",
      "Running time: 33.50897979736328 s\n"
     ]
    }
   ],
   "source": [
    "t1 = time.time()\n",
    "print(singleNumber2(a))\n",
    "t2 = time.time()\n",
    "print(\"Running time:\",str((t2-t1)),'s')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 在网上看到别的做法之一：(效率有了明显的提升)\n",
    "def singleNumber3(nums):\n",
    "    s = []\n",
    "    for each in nums:\n",
    "        if each not in s:\n",
    "            s.append(each)\n",
    "        else:\n",
    "            s.remove(each)\n",
    "    return s[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "111\n",
      "Running time: 0.007507801055908203 s\n"
     ]
    }
   ],
   "source": [
    "t1 = time.time()\n",
    "print(singleNumber3(a))\n",
    "t2 = time.time()\n",
    "print(\"Running time:\",str((t2-t1)),'s')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 据说把数组操作改成字典操作可以效率更高：\n",
    "def singleNumber4(nums):\n",
    "    s = {}\n",
    "    for each in nums:\n",
    "        if each in s.keys():\n",
    "            s.pop(each)\n",
    "        else:\n",
    "            s[each] = 1\n",
    "    return list(s.keys())[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "111\n",
      "Running time: 0.01701211929321289 s\n"
     ]
    }
   ],
   "source": [
    "t1 = time.time()\n",
    "print(singleNumber4(a))\n",
    "t2 = time.time()\n",
    "print(\"Running time:\",str((t2-t1)),'s')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# ！！！！！！！！！终极操作：异或运行（XOR）！！！！！！！！！！！！！还没搞懂。。。\n",
    "def singleNumber(nums):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    res = 0\n",
    "    for i in nums:\n",
    "        res^=i\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "111\n",
      "Running time: 0.006003618240356445 s\n"
     ]
    }
   ],
   "source": [
    "t1 = time.time()\n",
    "print(singleNumber(a))\n",
    "t2 = time.time()\n",
    "print(\"Running time:\",str((t2-t1)),'s')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 有一个更6的方法：利用问题的特殊性：直接求和相减\n",
    "def singleNumber0(nums):\n",
    "    return list(sum(list(set(nums))*2)-sum(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "111\n",
      "Running time: 0.005003690719604492 s\n"
     ]
    }
   ],
   "source": [
    "t1 = time.time()\n",
    "print(singleNumber(a))\n",
    "t2 = time.time()\n",
    "print(\"Running time:\",str((t2-t1)),'s')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 5.数组的交集\n",
    "给定两个数组，写一个方法来计算它们的交集。\n",
    "\n",
    "例如:\n",
    "给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].\n",
    "\n",
    "注意：\n",
    "\n",
    "       输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。\n",
    "       我们可以不考虑输出结果的顺序。\n",
    "\n",
    "跟进:\n",
    "\n",
    "    如果给定的数组已经排好序呢？你将如何优化你的算法？\n",
    "    如果 nums1 的大小比 nums2 小很多，哪种方法更优？\n",
    "    如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 我的方法：\n",
    "def intersect(nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        inter = []\n",
    "        if len(nums1)<=len(nums2):\n",
    "            for each in nums1:\n",
    "                if each in nums2:\n",
    "                    inter.append(each)\n",
    "                    nums2.remove(each)\n",
    "        else:\n",
    "            for each in nums2:\n",
    "                if each in nums1:\n",
    "                    inter.append(each)\n",
    "                    nums1.remove(each)\n",
    "        return inter\n",
    "# 这个方法有个问题：把原来的数组也改变了，因为使用了remove"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [1,1,2,3,4]\n",
    "b = [1,2,1]\n",
    "# intersect(a,b)\n",
    "# print(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "# collections方法： ------------这个方法还不太懂---------------\n",
    "import collections\n",
    "def intersect1(nums1,nums2):\n",
    "    return list((collections.Counter(nums1)&collections.Counter(nums2)).elements())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "intersect1(a,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 6.给数组代表的数字加K\n",
    "比如，[1,2,3]代表123，加上3，则变成126，应该输出[1,2,6]<br>\n",
    "难点在于，加上的数字可能导致进位，甚至可能多次进位，比如[1,9,8]加上3，变成[2,0,1].\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4, 1]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 我的思路：直接把数组变成数字，加上k之后，再转换回来：\n",
    "def plusK(nums,k): # 给nums代表的数字加k\n",
    "    l = len(nums)\n",
    "    real_num = 0\n",
    "    for i in range(l): # say:0,1,2\n",
    "        real_num += nums[-i-1]*pow(10,i)\n",
    "    return [int(x) for x in str(real_num+k)]\n",
    "\n",
    "plusK([1,2,3,4],7)\n",
    "\n",
    "## 嘿嘿，代码的效率超过了近90%的人，同时看了看，我的代码量比他们都少。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.移动数组中所有的0到末尾\n",
    "比如[0,1,3,0,2]-->[1,3,2,0,0]\n",
    "\n",
    "注意，其他的数组的相对位置不能变"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 12, 0, 0]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class MoveZero:\n",
    "    def my_method(self,nums):\n",
    "        n_0 = nums.count(0)\n",
    "        for i in range(n_0):\n",
    "            nums.remove(0)  # remove是移除数组的第一个匹配的项\n",
    "            nums.append(0)\n",
    "            #也可以下面这样\n",
    "            #nums.insert(len(nums),0) # 我不知道为何插入的位置不能写-1,\n",
    "        return nums\n",
    "    \n",
    "    # 下面是别人写的效率更高的答案：\n",
    "    def best_method(self,nums):\n",
    "        l,index = len(nums),0\n",
    "        for i in range(l):\n",
    "            if nums[i] != 0:\n",
    "                nums[index] = nums[i]\n",
    "                index += 1\n",
    "            # 经过上面的操作，所有非0项都转移到了前面。\n",
    "        nums[index:] = [0]*(l-index) # 一口气把数组后面的项都变成0\n",
    "        return nums\n",
    "moveZero = MoveZero()\n",
    "moveZero.best_method([0,1,3,0,12])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.在数组中找出和为某个指定值的两个数\n",
    "例如nums=[1,3,5,6],target=8,<br>\n",
    "由于是nums[1]+nums[2]=8,故应该返回[1,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 9]\n",
      "[0, 9]\n",
      "[0, 9]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    # 最笨的方法，两个循环去查找：\n",
    "    def two_sums1(self,nums,target): # 复杂度为n^2\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]+nums[j] == target:\n",
    "                    return [i,j]  \n",
    "    \n",
    "    # 转换成，已知其中一个数，找另一个数\n",
    "    # 因为从list中查找一个数，比直接扫描数组一遍要快。比如前者可以用二分法查找。\n",
    "    def two_sums2(self,nums,target): \n",
    "        for i in range(len(nums)):\n",
    "            other = target-nums[i]\n",
    "            if other in nums[i+1:]: \n",
    "                j = nums.index(other)\n",
    "                return [i,j]\n",
    "    \n",
    "    # 最快的方法，是构建一个字典，字典的查询速度是最快的:\n",
    "    # 循环的时候，就把键值对存进字典，同时查询是否有符合要求的数。复杂度为O(n)\n",
    "    def two_sums_best(self,nums,target):\n",
    "        nums_dict = {}\n",
    "        for i,x in enumerate(nums):\n",
    "            if target-x in nums_dict:\n",
    "                return [nums_dict[target-x],i]\n",
    "            nums_dict[x] = i\n",
    "                \n",
    "solution = Solution()\n",
    "nums=[1,2,3,10,1234,432,2343,151,353,232,1234,432,2343,5]\n",
    "target = 233\n",
    "print(solution.two_sums1(nums,target))\n",
    "print(solution.two_sums2(nums,target))\n",
    "print(solution.two_sums_best(nums,target))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.有效数独Sudoku\n",
    "判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。\n",
    "\n",
    "    数字 1-9 在每一行只能出现一次。\n",
    "    数字 1-9 在每一列只能出现一次。\n",
    "    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。\n",
    "<img src='sudoku.png'/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "board1 = [\n",
    "  [\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"],\n",
    "  [\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"],\n",
    "  [\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"],\n",
    "  [\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"],\n",
    "  [\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"],\n",
    "  [\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],\n",
    "  [\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"],\n",
    "  [\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"],\n",
    "  [\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]\n",
    "]\n",
    "board2 = [\n",
    "  [\"8\",\"3\",\".\",\".\",\"3\",\".\",\".\",\".\",\".\"],\n",
    "  [\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"],\n",
    "  [\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"],\n",
    "  [\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"],\n",
    "  [\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"],\n",
    "  [\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],\n",
    "  [\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"],\n",
    "  [\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"],\n",
    "  [\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]\n",
    "]\n",
    "\n",
    "class Solution:\n",
    "    # --------------我的方法，，太蠢了。\n",
    "    # 想办法把行、列、宫都挑出来。然后在判断其中每一个是不是符合要求的。\n",
    "    def check(self,l):\n",
    "        valid = True\n",
    "        n_dots = l.count(\".\")\n",
    "        n_num = len(l)-n_dots\n",
    "        n_uniq_num = len(list(set(l)))-1\n",
    "        if n_num != n_uniq_num:\n",
    "            valid = False\n",
    "        return valid\n",
    "\n",
    "    def concact(self,l):\n",
    "        s = []\n",
    "        for sub in l:\n",
    "            s = s+sub\n",
    "        return s\n",
    "\n",
    "    def my_isValidSudoku(self,board):\n",
    "        # 论如何创建一个固定长度的matrix\n",
    "        cols = [[] for _ in range(9)]\n",
    "        boxs = [[] for _ in range(9)]\n",
    "        print(\"检查rows...\")\n",
    "        for row in board:\n",
    "            if self.check(row)==False:\n",
    "                print(\"----False----\")\n",
    "                return False\n",
    "            else:\n",
    "                # 生成column的列表：\n",
    "                print(\"生成column的列表...\")\n",
    "                for i in range(9):\n",
    "                    cols[i].append(row[i])\n",
    "        #生成9个box：\n",
    "        print(\"生成9个box...\")\n",
    "        for i in range(1,10):\n",
    "            if 1<=i<=3:\n",
    "                boxs[i-1] = [row[3*i-3:3*i] for row in board[0:3]]\n",
    "            if 4<=i<=6:\n",
    "                boxs[i-1] = [row[3*(i-3)-3:3*(i-3)] for row in board[3:6]]\n",
    "            if 7<=i<=9:\n",
    "                boxs[i-1] = [row[3*(i-6)-3:3*(i-6)] for row in board[6:9]]\n",
    "        for col,box in zip(cols,boxs):\n",
    "            if self.check(col)==False or self.check(self.concact(box))==False:\n",
    "                print(\"----False----\")\n",
    "                return False\n",
    "        print(\"----TRUE!----\")\n",
    "        return True\n",
    "    \n",
    "    # =====================其他人的好方法=========================：\n",
    "    def isValidSudoku(self, board):\n",
    "        \"\"\"\n",
    "        思路：对行、列、宫创建一个集合（集合中的值都是唯一的）\n",
    "        然后遍历九宫格的每一个点（两重循环），查看在对于的行、列、宫中：\n",
    "        集合中出现过，就说明这个数独是无效的；\n",
    "        集合中没有，就添加进去。\n",
    "        \n",
    "        难点：\n",
    "        1. 利用 if some_item in set的这种思路来动态检查是否有重复元素\n",
    "        2. 如何用行、列的序号来表示九宫格的九宫的序号。\n",
    "        \"\"\"\n",
    "        # 创建包含9个set的list，确保放进去的都是唯一的\n",
    "        rows = [set([]) for _ in range(9)]\n",
    "        cols = [set([]) for _ in range(9)]\n",
    "        boxs = [set([]) for _ in range(9)]\n",
    "        \n",
    "        for r in range(9):\n",
    "            for c in range(9):\n",
    "                b = r//3*3 + c//3  # 也可以写：b = int(r/3)*3 + int(c/3)\n",
    "#                 print(\"box index: \",b)\n",
    "                if board[r][c] == \".\":\n",
    "                    continue\n",
    "                if board[r][c] in rows[r]:\n",
    "                    return False\n",
    "                if board[r][c] in cols[c]:\n",
    "                    return False\n",
    "                if board[r][c] in boxs[b]:\n",
    "                    return False\n",
    "                # 集合添加元素用add\n",
    "                rows[r].add(board[r][c])\n",
    "                cols[c].add(board[r][c])\n",
    "                boxs[b].add(board[r][c])\n",
    "        return True\n",
    "                \n",
    "        \n",
    "solution = Solution()\n",
    "solution.isValidSudoku(board1)\n",
    "solution.isValidSudoku(board2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.旋转图像\n",
    "给定一个 n × n 的二维矩阵表示一个图像。\n",
    "将图像顺时针旋转 90 度。\n",
    "\n",
    "说明：\n",
    "你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。\n",
    "\n",
    "示例：\n",
    "<pre>\n",
    "给定 matrix = \n",
    "[\n",
    "  [1,2,3],\n",
    "  [4,5,6],\n",
    "  [7,8,9]\n",
    "],\n",
    "\n",
    "原地旋转输入矩阵，使其变为:\n",
    "[\n",
    "  [7,4,1],\n",
    "  [8,5,2],\n",
    "  [9,6,3]\n",
    "]\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[7, 4, 1]\n",
      "[8, 5, 2]\n",
      "[9, 6, 3]\n"
     ]
    }
   ],
   "source": [
    "class Rotate:\n",
    "    def my_rotate(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: void Do not return anything, modify matrix in-place instead.\n",
    "        \n",
    "        我的发现：\n",
    "        旋转90°，是把原来的行都转化成列了；转置，也是把行都变成列了，这两者之间肯定有关系。\n",
    "        在纸上比划比划，就知道，顺时针旋转90°，相当于转置后，在把列的顺序颠倒。\n",
    "        \"\"\"\n",
    "        # 先转置：\n",
    "        length = len(matrix)\n",
    "        for i in range(length-1): # 不用到最后一行\n",
    "            for j in range(i+1,length): # 从i+1列开始到最后一列\n",
    "                matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]\n",
    "        # 然后水平颠倒\n",
    "        for r in range(length):\n",
    "            for c in range(length//2):\n",
    "                # the col to switch:\n",
    "                s = length - c - 1 \n",
    "                matrix[r][c],matrix[r][s] = matrix[r][s],matrix[r][c]\n",
    "        \n",
    "\n",
    "matrix = [\n",
    "  [1,2,3],\n",
    "  [4,5,6],\n",
    "  [7,8,9]\n",
    "]\n",
    "rotate = Rotate()\n",
    "rotate.my_rotate(matrix)\n",
    "\n",
    "for row in matrix:\n",
    "    print(row)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src='rotate.jpg'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Congratulations！\n",
    "## You have finished<Simple Algorithms about List\\>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
